/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sorting;

/**
 *
 * @author Akram Mellice
 */
public final class HeapSort<T extends Comparable> extends Sort<T> {

    private int heapSize = 0;

    public HeapSort(T[] array, Class<T> classType) {
        super(array, classType);
        heapSize = array.length;
    }

    private int left(int i) {
        return i * 2;
    }

    private int right(int i) {
        return i * 2 + 1;
    }

    private int parent(int i) {
        return (int) Math.floor(i / 2);
    }

    /**
     * O(lg n)
     * @param i 
     */
    private void maxHeapify(int i) {
        int l = left(i);
        int r = right(i);
        int largest = 0;
        if (l < heapSize && array[l].compareTo(array[i]) > 0) {
            largest = l;
        } else {
            largest = i;
        }
        if (r < heapSize && array[r].compareTo(array[largest]) > 0) {
            largest = r;
        }
        if (largest != i) {
            T tmp = array[i];
            array[i] = array[largest];
            array[largest] = tmp;
            maxHeapify(largest);
        }
    }
    
    /**
     * O(n) bottom-up
     */
    private void buildMaxHeap() {
        for(int i = array.length / 2; i >= 0; i--) {
            maxHeapify(i);
        }
    }

    /**
     * Sorts the array using Heap Sort
     * This sort is not stable
     * O(n lgn)
     */
    @Override
    public void sort() {
        buildMaxHeap();
        for(int i = array.length - 1; i > 0; i--) {
            T tmp = array[0];
            array[0] = array[i];
            array[i] = tmp;
            heapSize--;
            maxHeapify(0);
        }
    }
}
